Search for: All records

We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $\mathrm{ϵ<\#comment/>}$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi’s celebrated Regularity Lemma). We prove that $\mathrm{ϵ<\#comment/>}$-excellent sets exist for any $\mathrm{ϵ<\#comment/>}>\frac{1}{2}$in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\mathrm{ϵ<\#comment/>}>1/2^{2^k}$or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide. 

We find a strong separation between two natural families of simple rank one theories in Keisler's order: the theories $$T_m$$ reflecting graph sequences, which witness that Keisler's order has the maximum number of classes, and the theories $$T_{n,k}$$, which are the higher-order analogues of the triangle-free random graph. The proof involves building Boolean algebras and ultrafilters ``by hand'' to satisfy certain model theoretically meaningful chain conditions. This may be seen as advancing a line of work going back through Kunen's construction of good ultrafilters in ZFC using families of independent functions. We conclude with a theorem on flexible ultrafilters, and open questions. 

Dividing asks about inconsistency along indiscernible sequences. In order to study the finer structure of simple theories without much dividing, the authors recently introduced shearing, which essentially asks about inconsistency along generalized indiscernible sequences. Here we characterize the shearing of the random graph. We then use shearing to distinguish between the random graph and the theories $$T_{n,k}$$, the higher-order analogues of the triangle-free random graph. It follows that shearing is distinct from dividing in simple unstable theories, and distinguishes meaningfully between classes of simple unstable rank one theories. The paper begins with an overview of shearing, and includes open questions. 

This paper builds model-theoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a so-called context c. This leads to defining c-superstability, a syntactical notion, which includes supersimplicity as a special case. The main result is a separation theorem showing that for any countable context and any two theories T1, T2, such that T1 is c-superstable and T2 is c-unsuperstable, and for arbitrarily large mu, it is possible to build models of any theory interpreting both T1 and T2 whose restriction to tau(T1) is mu-saturated and whose restriction to tau(T2) is not aleph1-saturated. (This suggests “c-superstable” is really a dividing line.) The proof uses generalized Ehrenfeucht-Mostowski models, and along the way, we clarify the use of these techniques to realize certain types while omitting others. In some sense, shearing allows us to study the interaction of complexity coming from the usual notion of dividing in simple theories and the more combinatorial complexity detected by the general definition. This work is inspired by our recent progress on Keisler’s order, but does not use ultrafilters, rather aiming to build up the internal model theory of these classes. https://doi.org/10.1090/tran/8513